The present invention relates to a network relay apparatus and a packet distribution method, and particularly to a network relay apparatus and a packet distribution method that distribute input packets to a plurality of packet processors to thereby process the same in parallel and transfer the packets at high speed.
With greater sophistication of communication services using the Internet, such as video distribution, the sharing of data using P2P (Peer to Peer), etc., an increase in the amount of traffic has been abruptly advanced in recent years. An increase in communication speed has been required more than before. The processing load of a network relay apparatus such as a router, a gateway or the like in a network is becoming larger. An improvement in the throughput of the network relay apparatus is therefore urgently necessary.
Examples of techniques for improving packet throughput using a network relay apparatus include a parallel processing technique. The parallel processing technique executes processes such that a plurality of packet processors and a packet distribution unit provided in a stage prior to these are provided and packets are distributed to the packet processors to perform parallel processing thereof, thereby improving the packet throughput of the whole apparatus.
A round robin method is known as a first method for realizing the distribution of packets. The round robin method performs distributing packets in their arrival order. This method may vary in throughput speed depending on the length of each packet or the processing contents thereof. The method is therefore accompanied by a problem that the processing load cannot be dispersed uniformly.
There is thus provided an out-of-order method as a second method. The out-of-order method performs distributing each packet to a vacant packet processor. While uniform load distribution is performed in this method, among a series of packets continuously sent from a packet transfer source to a packet transfer destination, a packet having passed through a packet processor low in processing load may overtake a packet having passed through a packet processor high in processing load, inclusive of the round robin method, thereby reversing the order of the packets.
There is therefore provided a hash method as a third method. The hash method performs distributing packets in accordance with hash values calculated on the basis of header information. This is, for example, a method for calculating a hash function assuming, as an argument, a set of a source IP address of a packet, a destination IP address thereof, a protocol number thereof and the like taken as header information indicative of a flow, and determining a packet's distribution destination in accordance with the thus-obtained value (hash value). According to the present method, the order of each packet lying within the same flow is assured.
Japanese Patent Laid-Open Publication No. 2001-211203 provides the three methods referred to above. Upon dispersing the load using each of the round robin method and the out-of-order method, a transfer packet rearrangement processor is provided at an output stage to prevent the reversal of order of each packet, thereby rearranging the packets to the order at which the packet has been distributed and outputting them.
Japanese Patent Laid-Open Publication No. 2008-167305 has disclosed packet processing at a network apparatus. The patent document 2 discloses load dispersion by parallel processing at the network apparatus, but does not assure the prevention of the reversal of order of each packet.
Japanese Patent Laid-Open Publication No. 2004-221805 has disclosed load dispersion at a packet communication processor. The load dispersion described in Japanese Patent Laid-Open Publication No. 2004-221805 is based on statistical information. Japanese Patent Laid-Open Publication No. 2004-221805, however, does not assure the prevention of the reversal of order of each packet.
Japanese Patent Laid-Open Publication No. 2003-018198 has disclosed a packet transfer apparatus. The packet transfer apparatus however relates merely to parallelization of header processing.
A packet distribution method using a hash method will be explained with reference to FIGS. 1A and 1B. Here, FIGS. 1A and 1B are block diagrams for describing the packet distribution method using the hash method. In FIGS. 1A and 1B, only two packet processors 105 are described for the simplification of illustration. Only a packet distribution processor 103, processing waiting queues 104 and packet processors 105 in a network relay apparatus are shown in extracted form. Packets shown in circular form will be explained with reference to a processing waiting queue 104-1 of FIG. 1A. Packets A1, C1, A2 and C2 are being retained in the processing waiting queue 104-1 in this order. A means a flow A and C means a flow C. Numbers subsequent to A or C indicate flow's sequence numbers. Each processing waiting queue 104 is a so-called FIFO (First In First Out) memory, which inputs each packet from the left and outputs the same from the right.
In FIG. 1, the packet distribution processor 103 determines a hash value on the basis of header information of each received packet. The packet distribution processor 103 further specifies each of distribution destination packet processors 105-1 and 105-2 from the corresponding hash value. Here, packets that belong to the flows A and C are distributed to the processing waiting queue 104-1, and packets that belong to flows B are distributed to a processing waiting queue 104-2.
FIG. 1B shows the manner in which the time elapses slightly as compared with FIG. 1A and the traffic of each flow A increases. In the hash method, once-distributed packets continue to be processed by the same packet processor 105-1, but are not processed by the other packet processor 105-2. Therefore, the packet processor 105-2 does not process a flow C even though it is relatively light in load. There is thus a possibility that the flow C will be delayed and lose each packet due to the influence of each flow A.